package ljl.alg.jianzhioffer.round3.medium;

import java.util.ArrayDeque;

public class _31_validateStackSequences {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0;
        int j = 0;
        int[] tmp = new int[pushed.length];
        int t = 0;
        while (i < pushed.length) {
            tmp[t++] = pushed[i++];
            while (t > 0 && tmp[t - 1] == popped[j]) {
                t--;
                j++;
            }
        }
        return t == 0;
    }

    /**
     * 想复杂的版本，改了很多次，照着答案才改对了
     * 不过改到最后是上面那个版本，和答案已经一样了
     * */
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        int i = 0;
        int j = 0;
        int[] tmp = new int[pushed.length];
        int t = 0;
        while (i < pushed.length) {
            // 相等的话一起自增
            while (i < pushed.length && pushed[i] == popped[j]) {
                i++;
                j++;
            }
            // 不等的话，入栈
            while (i < pushed.length && pushed[i] != popped[j])
                tmp[t++] = pushed[i++];
            // 又相等了，但是先清库存，下一把再处理新数据
            // 又相等了，是先继续匹配，还是先清库存？为什么？
            while (t > 0 && tmp[t - 1] == popped[j - 1]) {
                t--;
                j++;
            }
        }
        return t == 0;
    }

    class lufei {

        public boolean validateStackSequences(int[] pushed, int[] popped) {
            ArrayDeque<Integer> stack = new ArrayDeque<>(pushed.length);
            int i = 0;
            for(int num : pushed) {
                stack.push(num);
                while(!stack.isEmpty() && stack.peek() == popped[i]) {
                    stack.pop();
                    i++;
                }
            }
            return stack.isEmpty();
        }

    }
}
